package q658_findClosestElements;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution_2 {
    /*
    代码量相对大一点 但也不难理解
    首先利用二分查找找到最后一个小于等于x的位置
    然后判断这个位置
    1 如果等于x 则res先加入x 然后将指针指向其两边 依次的加入数字
    2 如果不等于 则指针一个指向p 另一个为p + 1 依次的加入数字
     */
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        int p = binarySearchLow(arr, x);
        if (arr[p] == x) {
            res.add(x);
            int p1 = p - 1, p2 = p + 1;
            for (int i = 0; i < k - 1; i++) {
                if (p1 < 0) {
                    res.add(arr[p2++]);
                    continue;
                } else if (p2 >= arr.length) {
                    res.add(arr[p1--]);
                    continue;
                }
                if (Math.abs(arr[p1] - x) <= Math.abs(arr[p2] - x)) {
                    res.add(arr[p1--]);
                } else {
                    res.add(arr[p2++]);
                }
            }
        } else {
            int p1 = p, p2 = p + 1;
            for (int i = 0; i < k; i++) {
                if (p1 < 0) {
                    res.add(arr[p2++]);
                    continue;
                } else if (p2 >= arr.length) {
                    res.add(arr[p1--]);
                    continue;
                }
                if (Math.abs(arr[p1] - x) <= Math.abs(arr[p2] - x)) {
                    res.add(arr[p1--]);
                } else {
                    res.add(arr[p2++]);
                }
            }
        }
        res.sort(Comparator.comparingInt(a -> a));
        return res;
    }
    private int binarySearchLow(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 此题特殊点在于不能返回right为-1 或者说要对right = -1进行处理
        return Math.max(right, 0);
    }

}
